/**
 * 剑指 Offer 59 - I. 滑动窗口的最大值
 * https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function maxSlidingWindow(nums, k) {
  if (!k || !nums.length) {
    return [];
  }
  const stack = [];
  for (let i = 0; i < k; i += 1) {
    while (stack.length && nums[i] >= nums[stack[stack.length - 1]]) {
      stack.pop();
    }
    stack.push(i);
  }
  const result = new Array(nums.length - k + 1);
  result[0] = nums[stack[0]];
  for (let i = k; i < nums.length; i += 1) {
    if (stack[0] <= i - k) {
      stack.shift();
    }
    while (stack.length && nums[i] >= nums[stack[stack.length - 1]]) {
      stack.pop();
    }
    stack.push(i);
    result[i - k + 1] = nums[stack[0]];
  }
  return result;
}

console.log(displayBaseArray(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)) === '[3,3,5,5,6,7]');
